package algorithms.question.class16;

import common.util.MyUtil;

/**
 * https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 * <p>
 * 约瑟夫环问题
 * 给定一个链表头节点head，和一个正数m
 * 从头开始，每次数到m就杀死当前节点
 * 然后被杀节点的下一个节点从1开始重新数，
 * 周而复始直到只剩一个节点，返回最后的节点
 *
 * @author guichang
 * @date 2021/8/15
 */

@SuppressWarnings("all")
public class Code5_约瑟夫环问题 {

    public static void main(String[] args) {
        MyUtil.print(lastRemaining(5, 3));
    }

    public static int lastRemaining(int n, int m) {
        return getLive(n, m);
    }

    /**
     * 公式 前编号 = (后编号 + m - 1)%链表长度 + 1
     *
     * @param n 链表长度
     * @param m 每次数到m就杀
     * @return 最后存在的编号
     */
    public static int getLive(int n, int m) {
        if (n == 1) {
            return 1;
        }
        return (getLive(n - 1, m) + m - 1) % n + 1;
    }

}